import java.util.Stack;

/**
 * @program: leetcode042
 * @author: JCM
 * @create: 2023-03-27 22:29
 * @description:
 **/
public class Main {
    public int trap(int[] height) {
        if(height.length <= 2) return 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int ans = 0;
        for(int i = 1; i < height.length; i++) {
            // 当height[i] < 栈顶元素时,直接入栈
            if(height[i] < height[stack.peek()]) {
                stack.push(i);
            }else if(height[i] == height[stack.peek()]) {
                stack.pop();
                stack.push(i);
            }else {
                while(!stack.isEmpty() && height[stack.peek()] < height[i]) {
                    int mid = stack.pop();
                    if(!stack.isEmpty()) {
                        int h = Math.min(height[i],height[stack.peek()])-height[mid];
                        int w = i-stack.peek()-1;
                        int s = h*w;
                        ans += s;
                    }

                }
                stack.push(i);
            }
        }

        return ans;
    }
}
